﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Wintellect.PowerCollections;
using System.Collections;

namespace PriorityQueue
{
    class PriorityQueue
    {
        class Heap<T>
            where T : IComparable
        {
            public Heap()
            {
                heap = new List<T>();
                heap.Add(default(T));
            }

            public void Push(T element)
            {
                heap.Add(element);

                int last = heap.Count - 1;

                while (last != 1)
                {
                    int other = last / 2;

                    if (heap[last].CompareTo(heap[other]) < 0)
                    {
                        T temp = heap[last];
                        heap[last] = heap[other];
                        heap[other] = temp;
                    }
                    else
                    {
                        break;
                    }

                    last = other;
                }
            }

            public T Pop()
            {
                int last = heap.Count - 1;

                if (last == 0)
                {
                    throw new Exception("No more elements");
                }

                T result = heap[1];
                heap[1] = heap[last];
                heap.RemoveAt(last);
                --last;

                int current = 1;

                while ((current * 2) <= last)
                {
                    int other;
                    if ((current * 2) == last ||
                        (heap[current * 2].CompareTo(heap[(current * 2) + 1])) < 0)
                    {
                        other = current * 2;
                    }
                    else
                    {
                        other = (current * 2) + 1;
                    }

                    if (heap[current].CompareTo(heap[other]) > 0)
                    {
                        T temp = heap[current];
                        heap[current] = heap[other];
                        heap[other] = temp;
                    }
                    else
                    {
                        break;
                    }

                    current = other;
                }

                return result;
            }

            private List<T> heap;
        }

        class SortedMultiSetWrapper<T> : IEnumerable
            where T : IComparable
        {
            public SortedMultiSetWrapper()
            {
                set = new OrderedBag<T>();
            }

            public void Push(T element)
            {
                set.Add(element);
            }

            public T Pop()
            {
                T result = set.First();
                set.Remove(result);

                return result;
            }

            public T this[int index]
            {
                get
                {
                    return set.ElementAt(index);
                }
            }

            public IEnumerator GetEnumerator()
            {
                foreach (var item in set)
                {
                    yield return item;
                };
            }

            private OrderedBag<T> set;
        }

        static void Main(string[] args)
        {
            int MAX = 50;
            Random rand = new Random();
            //Heap<int> priorityQueue = new Heap<int>();
            SortedMultiSetWrapper<int> priorityQueue = new SortedMultiSetWrapper<int>();

            for (int i = 0; i < MAX; i++)
            {
                int elem = rand.Next(100);
                Console.WriteLine(elem);
                priorityQueue.Push(elem);
            }

            Console.WriteLine("--------------------------");
            foreach (var item in priorityQueue)
            {
                Console.WriteLine(item);
            }

            Console.WriteLine("--------------------------");
            for (int i = 0; i < MAX; i++)
            {
                Console.WriteLine(priorityQueue[i]);
            }

            Console.WriteLine("--------------------------");
            for (int i = 0; i < MAX; i++)
            {
                int elem = priorityQueue.Pop();
                Console.WriteLine(elem);
            }
        }
    }
}